//https://leetcode.cn/problems/multiply-strings/

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";

        int size1 = num1.size();
        int size2 = num2.size();
        string ret("0");
        //num2的每一个位跟num1相乘再相加
        for (int i = size2 - 1; i >= 0; i--)
        {
            string temp;
            int add = 0;  //表示拿取个位后剩下的另一位 即进位
            //如果num2不是个位 就要补0 差几位补几位
            for (int j = size2 - 1; j > i; j--)
            {
                temp.push_back('0');
            }

            int data2 = num2[i] - '0';
            //num2的每一位跟num1的每一位相乘 注意进位
            for (int j = size1 - 1; j >= 0; j--)
            {
                int data1 = num1[j] - '0';
                int sum = data1 * data2 + add;
                //存储和的个位
                temp.push_back((sum % 10) + '0');
                //保存剩下的值 加入下一轮的和
                add = sum / 10;
            }

            //运算结果仍存在进位
            while (add != 0)
            {
                temp.push_back((add % 10) + '0');
                add /= 10;
            }

            //字符串逆置
            reverse(temp.begin(), temp.end());

            //相加
            ret = addstring(ret, temp);

        }

        return ret;
    }

    //字符串相加
    string addstring(string& num1, string& num2) {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int count = 0;
        string s;
        while (end1 >= 0 || end2 >= 0)
        {
            int data1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int data2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int sum = data1 + data2 + count;
            count = sum / 10;
            sum %= 10;
            end1--;
            end2--;

            s.push_back(sum + '0');


        }

        if (count == 1)
            s.push_back('1');

        reverse(s.begin(), s.end());

        return s;
    }
};